/**
 * 双指针
 * 27.移除元素
 * 26.删除排序数组中的重复项
 * 283.移动零
 * 977.有序数组的平方
 * 844.比较含退格的字符串 细节多
 * **/

#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

template <class T>
void print(const T &t)
{
    class T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    //27.
    int removeElement(vector<int> &nums, int val)
    {
        int left = 0, right = 0;
        int n = nums.size();
        while (right < n) {
            if (nums[right] == val) {
                ++right;
                continue;
            }
            nums[left++] = nums[right++];
        }
        return left;
    }
    //26.
    int removeDuplicates(vector<int> &nums)
    {
        int left = 0, right = 1;
        int n = nums.size();
        while (right < n) {
            if (nums[left] == nums[right]) {
                ++right;
                continue;
            }
            nums[++left] = nums[right++];
        }
        return left + 1;
    }
    //283.
    void moveZeroes(vector<int> &nums)
    {
        int left = 0, right = 0;
        int n = nums.size();
        // while (right < n) {
        //     if (nums[right] != 0) {
        //         nums[left++] = nums[right++];
        //         continue;
        //     }
        //     ++right;
        // }
        // for (int i = left; i < n; ++i) {
        //     nums[i] = 0;
        // }
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums[left], nums[right]);
                ++left;
            }
            ++right;
        }
    }
    //977.
    vector<int> sortedSquares(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> ret(n, 0);
        int left = 0, right = n - 1;
        int pos = n - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                ret[pos--] = nums[left] * nums[left];
                ++left;
            } else {
                ret[pos--] = nums[right] * nums[right];
                --right;
            }
        }
        return ret;
    }
    //844.
    bool backspaceCompare(string s, string t)
    {
#if 0
        //很容易想到用栈模拟 时间O(N),空间O(N)
        stack<char> stkS;
        stack<char> stkT;
        for (char &ch : s) {
            if (ch != '#') {
                stkS.push(ch);
            } else if (!stkS.empty()) {
                stkS.pop();
            }
        }
        for (char &ch : t) {
            if (ch != '#') {
                stkT.push(ch);
            } else if (!stkT.empty()) {
                stkT.pop();
            }
        }
        //比较两个栈
        while (!stkS.empty() && !stkT.empty()) {
            if (stkS.top() != stkT.top()) {
                return false;
            }
            stkS.pop();
            stkT.pop();
        }
        return stkS.empty() && stkT.empty();
#endif
        // 双指针 O(1)空间
        // 总结一下就是遇到‘#’继续左移，直到‘#’消耗完
        int i = s.size() - 1, j = t.size() - 1;
        int counti = 0, countj = 0; // 从后往前遇到的‘#’个数
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s[i] == '#') {
                    ++counti;
                    --i;
                } else if (counti > 0) {
                    --counti;
                    --i;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (t[j] == '#') {
                    ++countj;
                    --j;
                } else if (countj > 0) {
                    --countj;
                    --j;
                } else {
                    break;
                }
            }
            // cout << i << endl;
            // cout << j << endl;
            // cout << s[i] << endl;//越界
            if (i >= 0 && j >= 0) {
                if (s[i] != t[j])
                    return false;
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            --i;
            --j;
        }
        return true;
    }
};

Solution solve = Solution();

void test27()
{
    vector<int> nums = {0, 1, 2, 2, 3, 0, 4, 2};
    int val = 2;
    print(nums);
    cout << solve.removeElement(nums, val) << endl;
    print(nums);
}

void test26()
{
    vector<int> nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    print(nums);
    cout << solve.removeDuplicates(nums) << endl;
    print(nums);
}

void test283()
{
    vector<int> nums = {0, 1, 2, 2, 3, 0, 4, 2};
    // vector<int> nums = {0, 0, 0};
    print(nums);
    solve.moveZeroes(nums);
    print(nums);
}

void test977()
{
    vector<int> nums = {-7, -3, 2, 3, 11};
    print(nums);
    print(solve.sortedSquares(nums));
}

void test844()
{
    // string s = "a##c", t = "#a#c";
    // string s = "a#c", t = "b";
    string s = "ab##", t = "c#d#";
    cout << solve.backspaceCompare(s, t) << endl;
}

int main()
{
    // test27();
    // test26();
    // test283();
    // test977();
    test844();
    return 0;
}